package com.gitee.feizns.explore.data_structure.tree.bs.hard;

import com.gitee.feizns.explore.data_structure.tree.bs.easy.TreeNode;

import java.util.Arrays;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;

/**
 * 面试题 04.09. 二叉搜索树序列
 * @author feizns
 * @since 2020/3/23
 */
public class BSTSequences {

    public static void main(String[] args) {
        BSTSequences b = new BSTSequences();
        List<List<Integer>> lists = b.BSTSequences(create());
        System.out.println(lists);
    }

    private static TreeNode create() {
        TreeNode ret = new TreeNode(1);
        ret.left = new TreeNode(2);
        return ret;
    }

    public List<List<Integer>> BSTSequences(TreeNode root) {
        List<List<Integer>> lists = helper(root);
        if ( lists.isEmpty() )
            lists.add(Collections.emptyList());
        return lists;
    }

    private List<List<Integer>> helper(TreeNode root) {
        List<List<Integer>> ret = new LinkedList<>();
        if ( root != null ) {
            List<List<Integer>> lef = helper(root.left);
            List<List<Integer>> rig = helper(root.right);
            if ( !lef.isEmpty() && !rig.isEmpty() ) {
                for (List<Integer> list : lef) {
                    for (List<Integer> ins : rig) {
                        List<Integer> tmp = new LinkedList<>(list);
                        tmp.addAll(ins);
                        tmp.add(0, root.val);
                        ret.add(tmp);
                    }
                }
                for (List<Integer> list : rig) {
                    for (List<Integer> ins : lef) {
                        List<Integer> tmp = new LinkedList<>(list);
                        tmp.addAll(ins);
                        tmp.add(0, root.val);
                        ret.add(tmp);
                    }
                }
            } else if ( lef.isEmpty() && rig.isEmpty() ) {
                ret.add(Arrays.asList(root.val));
            } else if ( lef.isEmpty() ) {
                for (List<Integer> list : rig) {
                    List<Integer> tmp = new LinkedList<>(list);
                    tmp.add(0, root.val);
                    ret.add(tmp);
                }
            } else {
                for (List<Integer> list : lef) {
                    List<Integer> tmp = new LinkedList<>(list);
                    tmp.add(0, root.val);
                    ret.add(tmp);
                }
            }
        }
        return ret;
    }

}
